home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / C⁄C++ / Xconq 7.0d37 / source / kernel / mkterr.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-01-31  |  24.3 KB  |  903 lines  |  [TEXT/KAHL]
  1. /* Terrain generation for Xconq.
  2.    Copyright (C) 1986, 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995
  3.    Stanley T. Shebs.
  4.  
  5. Xconq is free software; you can redistribute it and/or modify
  6. it under the terms of the GNU General Public License as published by
  7. the Free Software Foundation; either version 2, or (at your option)
  8. any later version.  See the file COPYING.  */
  9.  
  10. /* This is the collection of terrain generation methods. */
  11.  
  12. /* Fractal terrain generation. */
  13.  
  14. /* The process is actually done for elevation and water separately, then
  15.    the terrain type is derived from looking at both together. */
  16.  
  17. #include "conq.h"
  18.  
  19. /* This bounds the range of high and low spots. */
  20.  
  21. #define MAXALT 4000
  22.  
  23. /* The following dynamically allocated arrays must be ints, since a area
  24.    may have >32K cells. */
  25.  
  26. int *histo;             /* histogram array */
  27. int *alts;              /* percentile for each elevation */
  28. int *wets;              /* percentile for level of moisture */
  29.  
  30. /* Area scratch layers are used as: relief = tmp1, moisture = tmp2,
  31.    aux = tmp3 */
  32.  
  33. int stepsize = 20;
  34.  
  35. int partdone;
  36.  
  37. /* This variable records the number of cells that didn't match any of the
  38.    terrain type percentiles. */
  39.  
  40. static int numholes;
  41.  
  42. static void make_blobs PROTO ((short *layer, int numblobs, int blobradius, int blobalt));
  43. static void limit_layer PROTO ((short *layer, int hi, int lo));
  44. static void smooth_layer PROTO ((short *layer, int times));
  45. static void percentile PROTO ((short *layer, int *percentiles));
  46. static void compose_area PROTO ((void));
  47. static int terrain_from_percentiles PROTO ((int x, int y));
  48. static int dig_maze_path PROTO ((int x1, int y1, int dir1));
  49. static int num_open_adj PROTO ((int x, int y));
  50. static int random_solid_terrain PROTO ((void));
  51. static int random_room_terrain PROTO ((void));
  52. static int random_passage_terrain PROTO ((void));
  53. static int high_point PROTO ((int x, int y));
  54. static int water_point PROTO ((int x, int y));
  55. static int bay_point PROTO ((int x, int y));
  56. static void set_room_interior PROTO ((int x, int y));
  57. static void name_highest_peaks PROTO ((Obj *parms));
  58. static void name_lakes PROTO ((Obj *parms));
  59. static char *name_feature_at PROTO ((int x, int y, char *typename));
  60.  
  61. /* The main function goes through a heuristically-determined process */
  62. /* (read: I dinked until I liked the results) to make a area. */
  63.  
  64. /* Should add a cheap erosion simulator. */
  65.  
  66. int
  67. make_fractal_terrain()
  68. {
  69.     int actualcells, altnumblobs, altblobradius, altblobalt;
  70.     int wetnumblobs, wetblobradius, wetblobalt;
  71.  
  72.     /* Don't run if terrain is already present. */
  73.     if (terrain_defined()) return FALSE;
  74.     /* Note that we may still want this even if only one ttype defined,
  75.        since elevs may still vary usefully. */
  76.     /* Heuristic limit - this algorithm would get weird on small areas */
  77.     if (area.width < 9 || area.height < 9) {
  78.     init_warning("cannot generate fractal terrain for a %d x %d area",
  79.              area.width, area.height);
  80.     return FALSE;
  81.     }
  82.     Dprintf("Going to make fractal terrain ...\n");
  83.     allocate_area_scratch(3);
  84.     histo  = (int *) xmalloc(MAXALT * sizeof(int));
  85.     alts   = (int *) xmalloc(MAXALT * sizeof(int));
  86.     wets   = (int *) xmalloc(MAXALT * sizeof(int));
  87.     announce_lengthy_process("Making fractal terrain");
  88.     /* Need a rough estimate of how much work involved, so can do progress. */
  89.     if (g_alt_blob_density() > 0) {
  90.     actualcells = (g_alt_blob_size() * area_cells()) / 10000;
  91.     altblobradius = isqrt((actualcells * 4) / 3) / 2;
  92.     altnumblobs = (g_alt_blob_density() * area_cells()) / 10000;
  93.     altblobalt = g_alt_blob_height();
  94.     }
  95.     if (g_wet_blob_density() > 0) {
  96.     actualcells = (g_wet_blob_size() * area_cells()) / 10000;
  97.     wetblobradius = isqrt((actualcells * 4) / 3) / 2;
  98.     wetnumblobs = (g_wet_blob_density() * area_cells()) / 10000;
  99.     wetblobalt = g_wet_blob_height();
  100.     }
  101.     if (g_alt_blob_density() > 0) {
  102.     /* Build a full relief area. */
  103.     partdone = 0;
  104.     make_blobs(area.tmp1, altnumblobs, altblobradius, altblobalt);
  105.     /* Run the requested number of smoothing steps. */
  106.     partdone += stepsize;
  107.     smooth_layer(area.tmp1, g_alt_smoothing());
  108.     percentile(area.tmp1, alts);
  109.     }
  110.     if (g_wet_blob_density() > 0) {
  111.     /* Build a "moisture relief" area. */
  112.     partdone += stepsize;
  113.     make_blobs(area.tmp2, wetnumblobs, wetblobradius, wetblobalt);
  114.     partdone += stepsize;
  115.     smooth_layer(area.tmp2, g_wet_smoothing());
  116.     percentile(area.tmp2, wets);
  117.     }
  118.     /* Put it all together. */
  119.     partdone += stepsize;
  120.     compose_area();
  121.     add_edge_terrain();
  122.     /* Free up what we don't need anymore. */
  123.     free(histo);
  124.     free(alts);
  125.     free(wets);
  126.     finish_lengthy_process();
  127.     /* Report on the substitutions made. */
  128.     if (numholes > 0) {
  129.     init_warning("no possible terrain for %d cells, made them into %s",
  130.              numholes, t_type_name(0));
  131.     }
  132.     return TRUE;
  133. }
  134.  
  135. static void
  136. make_blobs(layer, numblobs, blobradius, blobalt)
  137. short *layer;
  138. int numblobs, blobradius, blobalt;
  139. {
  140.     int x0, y0, x1, y1, x2, y2, updown, x, y, xw;
  141.     long maxdz, i, dz, oz;
  142.  
  143.     /* Init everything to the middle of the raw altitude range. */
  144.     for_all_cells(x, y) aset(layer, x, y, MAXALT/2);
  145.     numblobs = max(1, numblobs);
  146.     maxdz = min(max(1, blobalt), MAXALT/2);
  147.     Dprintf("Making %d blobs of radius %d max-dz %d...\n",
  148.         numblobs, blobradius, maxdz);
  149.     /* Now lay down blobs. */
  150.     for (i = 0; i < numblobs; ++i) {
  151.     if (i % 100 == 0) {
  152.         announce_progress(partdone + (stepsize * i) / numblobs);
  153.     }
  154.     /* Decide whether we're making a hole or a hill. */
  155.     updown = (flip_coin() ? 1 : -1);
  156.     /* Pick a center for the bump. */
  157.     random_point(&x0, &y0);
  158.     if (blobradius <= 0) {
  159.         /* Special case for one-cell blobs. */
  160.         aadd(layer, x0, y0, updown * maxdz);
  161.     } else {
  162.         /* Compute the LL corner. */
  163.         x1 = x0 - blobradius;  y1 = y0 - blobradius;
  164.         /* Compute the UR corner. */
  165.         x2 = x0 + blobradius;  y2 = y0 + blobradius;
  166.         /* Raise/lower all the cells within this bump. */
  167.         for (y = y1; y <= y2; ++y) {
  168.         for (x = x1; x <= x2; ++x) {
  169.             xw = wrapx(x);
  170.             if ((x - x1 + y - y1 > blobradius)
  171.             && (x2 - x + y2 - y > blobradius)) {
  172.             /* skip points outside the area */
  173.             if (in_area(x, y)) {
  174.                 oz = aref(layer, xw, y);
  175. #if 1 /* ndef MPW_C */
  176.                 /* Add some variation within the bump. */ 
  177.                 dz = updown * (maxdz + xrandom(maxdz/2));
  178.                 /* If dz is really extreme, cut it down. */
  179.                 if (!between(0, oz + dz, MAXALT)) dz /= 2;
  180. #else
  181.                 dz = updown * maxdz / 2;
  182. #endif
  183.                 aset(layer, xw, y, oz + dz);
  184.             }
  185.             }
  186.         }
  187.         }
  188.     }
  189.     }
  190.     /* Adding and subtracting might have got out of hand. */
  191.     limit_layer(layer, MAXALT-1, 0); 
  192. }
  193.  
  194. /* Ensure that area values stay within given range. */
  195.  
  196. static void
  197. limit_layer(layer, hi, lo)
  198. short *layer;
  199. int hi, lo;
  200. {
  201.     int x, y, m;
  202.     
  203.     for_all_cells(x, y) {
  204.     m = aref(layer, x, y);
  205.     aset(layer, x, y, max(lo, min(m, hi)));
  206.     }
  207. }
  208.  
  209. /* Average each cell with its neighbors, using tmp3 as scratch layer. */
  210.  
  211. static void
  212. smooth_layer(layer, times)
  213. short *layer;
  214. int times;
  215. {
  216.     int i, x, y, nx, px, dir, x1, y1, ndirs;
  217.     long sum;
  218.  
  219.     for (i = 0; i < times; ++i) {
  220.     Dprintf("Smoothing...\n");
  221.     for (x = 0; x < area.width; ++x) {
  222.         nx = wrapx(x + 1);
  223.         px = wrapx(x - 1);
  224.         for (y = 0; y < area.height; ++y) {
  225.         if (in_area(x, y)) {
  226.             sum = aref(layer, x, y);
  227.             if (inside_area(x, y) /* and hex geometry */) {
  228.             sum += aref(layer, x, y+1);
  229.             sum += aref(layer, nx, y);
  230.             sum += aref(layer, nx, y-1);
  231.             sum += aref(layer, x, y-1);
  232.             sum += aref(layer, px, y);
  233.             sum += aref(layer, px, y+1);
  234.             sum /= (NUMDIRS + 1);
  235.             } else {
  236.             /* Otherwise, use a slower but more general algorithm. */
  237.             ndirs = 0;
  238.             for_all_directions(dir) {
  239.                 if (point_in_dir(x, y, dir, &x1, &y1)) {
  240.                 sum += aref(layer, x1, y1);
  241.                 ++ndirs;
  242.                 }
  243.             }
  244.             if (ndirs > 0)
  245.               sum /= ndirs;
  246.             }
  247.             set_tmp3_at(x, y, sum);
  248.         }
  249.         }
  250.     }
  251.     for (x = 0; x < area.width; ++x) {
  252.         for (y = 0; y < area.height; ++y) {
  253.         aset(layer, x, y, tmp3_at(x, y));
  254.         }
  255.     }
  256.     announce_progress(partdone + (stepsize * i) / times);
  257.     }
  258. }
  259.  
  260. /* Terrain types are specified in terms of percentage cover on a area, so
  261.    for instance the Earth is 70% sea.  Since each of several types will have
  262.    its own percentages (both for elevation and moisture), the simplest thing
  263.    to do is to calculate the percentile for each raw elevation and moisture
  264.    value, and save them all away.  */
  265.  
  266. /* Percentile computation is inefficient, should be done incrementally
  267.    somehow instead of with * and / */
  268.  
  269. static void
  270. percentile(layer, percentiles)
  271. short *layer;
  272. int *percentiles;
  273. {
  274.     int i, x, y, total;
  275.     
  276.     Dprintf("Computing percentiles...\n");
  277.     limit_layer(layer, MAXALT-1, 0);
  278.     for (i = 0; i < MAXALT; ++i) {
  279.     histo[i] = 0;
  280.     percentiles[i] = 0;
  281.     }
  282.     /* Make the basic histogram, counting only the inside. */
  283.     for_all_interior_cells(x, y) {
  284.     if (inside_area(x, y)) {
  285.         ++histo[aref(layer, x, y)];
  286.     }
  287.     }
  288.     /* Integrate over the histogram */
  289.     for (i = 1; i < MAXALT; ++i)
  290.     histo[i] += histo[i-1];
  291.     /* Total here should actually be same as number of cells in the area */
  292.     total = histo[MAXALT-1];
  293.     /* Compute the percentile position */
  294.     for (i = 0; i < MAXALT; ++i) {
  295.     percentiles[i] = (100 * histo[i]) / total;
  296.     }
  297. }
  298.  
  299. /* Final creation and output of the area. */
  300.  
  301. static void
  302. compose_area()
  303. {
  304.     int x, y, rawelev, elev, t, elevrange[MAXTTYPES];
  305.  
  306.     Dprintf("Assigning terrain types to cells...\n");
  307.     /* Make the terrain layer itself. */
  308.     allocate_area_terrain();
  309.     numholes = 0;
  310.     for_all_interior_cells(x, y) {
  311.     t = terrain_from_percentiles(x, y);
  312.     set_terrain_at(x, y, t);
  313.     }
  314.     if (!world_is_flat()) {
  315.         /* Compute elevation variations of terrain. */
  316.         for_all_terrain_types(t) {
  317.             elevrange[t] = t_elev_max(t) - t_elev_min(t);
  318.         }
  319.         if (!elevations_defined()) {
  320.         allocate_area_elevations();
  321.        }
  322.     for_all_cells(x, y) {
  323.         t = terrain_at(x, y);
  324.         rawelev = tmp1_at(x, y);
  325.         elev = ((rawelev * elevrange[t]) / MAXALT) + t_elev_min(t);
  326.         set_elev_at(x, y, elev);
  327.     }
  328.     }
  329. }
  330.  
  331. /* Compute the actual terrain types.  This is basically a process of
  332.    checking the percentile limits on each type against what is actually
  333.    there. */
  334.  
  335. static int
  336. terrain_from_percentiles(x, y)
  337. int x, y;
  338. {
  339.     int t, rawalt = tmp1_at(x, y), rawwet = tmp2_at(x, y);
  340.  
  341.     if (numttypes == 1)
  342.       return 0;
  343.     for_all_terrain_types(t) {
  344.     if (t_is_cell(t)
  345.         && between(t_alt_min(t), alts[rawalt], t_alt_max(t))
  346.         && between(t_wet_min(t), wets[rawwet], t_wet_max(t))) {
  347.         return t;
  348.     }
  349.     }
  350.     /* No terrain maybe not an error, so just count and summarize later. */
  351.     ++numholes;
  352.     return 0;
  353. }
  354.  
  355. /* Totally random (with weighting) terrain generation, as well as
  356.    random elevations. */
  357.  
  358. int
  359. make_random_terrain()
  360. {
  361.     int t, x, y, i, j, divvy, occurtable[100], elevrange;
  362.  
  363.     if (terrain_defined()) return FALSE;
  364.     announce_lengthy_process("Making random terrain");
  365.     Dprintf("Assigning terrain types...\n");
  366.     /* (should fix this to allow any range of occurrence values) */
  367.     i = 0;
  368.     for_all_terrain_types(t) {
  369.     if (t_occurrence(t) > 0) {
  370.         for (j = 0; j < t_occurrence(t); ++j) {
  371.         if (i < 100) occurtable[i++] = t;
  372.         }
  373.     } else {
  374.         divvy++;
  375.     }
  376.     }
  377.     if (i == 0) {
  378.         for (i = 0; i < 100; ++i)
  379.           occurtable[i] = 0;
  380.     }
  381.     allocate_area_terrain();
  382.     /* Overwrite already-defined elevs? */
  383.     if (!elevations_defined() && !world_is_flat())
  384.       allocate_area_elevations();
  385.     for_all_interior_cells(x, y) {
  386.     t = occurtable[xrandom(100)];
  387.     set_terrain_at(x, y, t);
  388.     if (elevations_defined() && !world_is_flat()) {
  389.         elevrange = t_elev_max(t) - t_elev_min(t);
  390.         set_elev_at(x, y, xrandom(elevrange) + t_elev_min(t));
  391.     }
  392.     }
  393.     /* Make sure the border of the area has something in it. */
  394.     add_edge_terrain();
  395.     finish_lengthy_process();
  396.     return TRUE;
  397. }
  398.  
  399. /* Method that is wired to be as close to earth as possible. */
  400.  
  401. /* (need to compute scale, get avg elevation and rainfall) */
  402.  
  403. int seatype = -1;
  404. int landtype = -1;
  405.  
  406. int
  407. make_earthlike_terrain()
  408. {
  409.     int t, x, y, elevrange;
  410.  
  411.     if (terrain_defined()) return FALSE;
  412.     Dprintf("Categorizing terrain types...\n");
  413.     for_all_terrain_types(t) {
  414.         if (strcmp("sea", t_type_name(t)) == 0) seatype = t;
  415.         if (strcmp("plains", t_type_name(t)) == 0) landtype = t;
  416.         /* etc */
  417.     }
  418.     if (seatype <= 0 || landtype <= 0) {
  419.         Dprintf("can't find earthlike terrain types");
  420.         return FALSE;
  421.     }
  422.     announce_lengthy_process("Making Earth-like terrain");
  423.     allocate_area_terrain();
  424.     /* Overwrite already-defined elevs? */
  425.     if (!elevations_defined() && !world_is_flat())
  426.       allocate_area_elevations();
  427.     elevrange = maxelev - minelev;
  428.     for_all_cells(x, y) {
  429.     if (inside_area(x, y)) {
  430.         set_terrain_at(x, y, (flip_coin() ? seatype : landtype));
  431.         if (elevations_defined() && !world_is_flat()) {
  432.             if (terrain_at(x, y) == seatype) {
  433.             set_elev_at(x, y, 0);
  434.             } else {
  435.             set_elev_at(x, y, xrandom(elevrange - 1) + 1);
  436.             }
  437.         }
  438.     }
  439.     }
  440.     /* Make sure the border of the area has something in it. */
  441.     add_edge_terrain();
  442.     finish_lengthy_process();
  443.     return TRUE;
  444. }
  445.  
  446. /* Maze terrain generation.  */
  447.  
  448. int numsolidtypes = 0;
  449. int numroomtypes = 0;
  450. int numpassagetypes = 0;
  451.  
  452. int sumsolidoccur = 0;
  453. int sumroomoccur = 0;
  454. int sumpassageoccur = 0;
  455.  
  456. int solidtype = NONTTYPE;
  457. int roomtype = NONTTYPE;
  458. int passagetype = NONTTYPE;
  459.  
  460. int numpassagecells = 0;
  461.  
  462. static void
  463. set_room_interior(x, y)
  464. int x, y;
  465. {
  466.     set_terrain_at(x, y, random_room_terrain());
  467. }
  468.  
  469. int
  470. make_maze_terrain()
  471. {
  472.     int t, x, y, x1, y1, i;
  473.     int dir, n;
  474.     int numcells, tries = 0;
  475.     int roomcells, roomradius, numrooms;
  476.     int numsolidcells = 0, numpassagecellsneeded;
  477.  
  478.     if (terrain_defined()) return FALSE;
  479.     for_all_terrain_types(t) {
  480.         if ((n = t_occurrence(t)) > 0) {
  481.         sumsolidoccur += n;
  482.         ++numsolidtypes;
  483.         solidtype = t;
  484.         }
  485.         if ((n = t_maze_room_occurrence(t)) > 0) {
  486.         sumroomoccur += n;
  487.         ++numroomtypes;
  488.         roomtype = t;
  489.         }
  490.         if ((n = t_maze_passage_occurrence(t)) > 0) {
  491.         sumpassageoccur += n;
  492.         ++numpassagetypes;
  493.         passagetype = t;
  494.         }
  495.     }
  496.     if (numsolidtypes + numroomtypes + numpassagetypes < 2) {
  497.         init_warning("No types to make maze with");
  498.         return FALSE;
  499.     }
  500.     announce_lengthy_process("Making maze terrain");
  501.     allocate_area_terrain();
  502.     /* Fill in the area with solid terrain. */
  503.     for_all_cells(x, y) {
  504.     set_terrain_at(x, y, random_solid_terrain());
  505.     }
  506.     /* Set the edges properly. */
  507.     add_edge_terrain();
  508.     numcells = area_cells();
  509.     if (g_maze_room() > 0) {
  510.     roomcells = 7;
  511.     roomradius = 1;
  512.     numrooms = ((numcells * g_maze_room()) / 10000) / roomcells;
  513.     for (i = 0; i < numrooms; ++i) {
  514.         random_point(&x1, &y1);
  515.         apply_to_area(x1, y1, roomradius, set_room_interior);
  516.     }
  517.     }
  518.     for_all_interior_cells(x, y) {
  519.         if (t_occurrence(terrain_at(x, y)) > 0) ++numsolidcells;
  520.     }
  521.     if (g_maze_passage() > 0) {
  522.       numpassagecellsneeded = (numcells * g_maze_passage()) / 10000;
  523.       while (numpassagecells < numpassagecellsneeded && tries++ < 500) {
  524.         random_point(&x1, &y1);
  525.         if (t_occurrence(terrain_at(x1, y1)) > 0) {
  526.         set_terrain_at(x1, y1, random_passage_terrain());
  527.         dir = random_dir();
  528.         dig_maze_path(x1, y1, dir);
  529.         dig_maze_path(x1, y1, opposite_dir(dir));
  530.         }
  531.       }
  532.     }
  533.     /* Make sure the border of the area is fixed up. */
  534.     add_edge_terrain();
  535.     finish_lengthy_process();
  536.     return TRUE;
  537. }
  538.  
  539. static int
  540. dig_maze_path(x1, y1, dir1)
  541. int x1, y1, dir1;
  542. {
  543.     int found;
  544.     int x, y, iter = 0, dir, dir2, nx, ny, nx2, ny2;
  545.     int dug = 0;
  546.     
  547.     while (!inside_area(x1+dirx[dir1], y1+diry[dir1])) {
  548.     dir1 = random_dir();
  549.     }
  550.     dir = dir1;
  551.     x = x1;  y = y1;
  552.     while (++iter < 500) {
  553.     point_in_dir(x, y, dir, &nx, &ny);
  554.     if (!inside_area(nx, ny)) break;
  555.     if (t_occurrence(terrain_at(nx, ny)) > 0
  556.         && num_open_adj(nx, ny) == 1) {
  557.         set_terrain_at(nx, ny, random_passage_terrain());
  558.         ++numpassagecells;
  559.         ++dug;
  560.     } else {
  561.         found = FALSE;
  562.         for_all_directions(dir2) {
  563.         point_in_dir(x, y, dir2, &nx2, &ny2);
  564.         if (inside_area(nx2, ny2)
  565.             && t_occurrence(terrain_at(nx2, ny2)) > 0
  566.             && num_open_adj(nx2, ny2) == 1) {
  567.             set_terrain_at(nx2, ny2, random_passage_terrain());
  568.             ++numpassagecells;
  569.             ++dug;
  570.             found = TRUE;
  571.             dir = dir2;
  572.             break;
  573.         }
  574.         }
  575.         if (!found) {
  576.         return dug;
  577.         }
  578.     }
  579.     if (probability(20)) {
  580.         dig_maze_path(nx, ny, left_dir(dir));
  581.         dig_maze_path(nx, ny, right_dir(dir));
  582.         return dug;
  583.     } else {
  584.         x = nx;  y = ny;
  585.         dir = (probability(50) ? dir : random_dir());
  586.     }
  587.     }
  588.     return dug;
  589. }
  590.  
  591. static int
  592. num_open_adj(x, y)
  593. int x, y;
  594. {
  595.     int dir, rslt = 0, nx, ny;
  596.  
  597.     for_all_directions(dir) {
  598.     point_in_dir(x, y, dir, &nx, &ny);
  599.     if (t_maze_room_occurrence(terrain_at(nx, ny)) > 0
  600.         || t_maze_passage_occurrence(terrain_at(nx, ny)) > 0) ++rslt;
  601.     }
  602.     return rslt;
  603. }
  604.  
  605. static int
  606. random_solid_terrain()
  607. {
  608.     if (numsolidtypes == 1) return solidtype;
  609.     return (xrandom(numttypes));
  610. }
  611.  
  612. static int
  613. random_room_terrain()
  614. {
  615.     if (numroomtypes == 1) return roomtype;
  616.     return (xrandom(numttypes));
  617. }
  618.  
  619. static int
  620. random_passage_terrain()
  621. {
  622.     if (numpassagetypes == 1) return passagetype;
  623.     return (xrandom(numttypes));
  624. }
  625.  
  626. /* This method adds some randomly named geographical features. */
  627.  
  628. /* (This needs to interact properly with convex region finder eventually) */
  629.  
  630. int
  631. name_geographical_features()
  632. {
  633.     char *classname;
  634.     Obj *rest;
  635.  
  636.     /* If we got features from file or somewhere, don't overwrite them. */
  637.     if (features_defined())
  638.       return FALSE;
  639.     /* We need to have some terrain to work from. */
  640.     if (!terrain_defined())
  641.       return FALSE;
  642.     /* If no feature types requested, don't make any. */
  643.     if (g_feature_types() == lispnil)
  644.       return FALSE;
  645.     announce_lengthy_process("Adding geographical features");
  646.     Dprintf("Adding geographical features...\n");
  647.     /* Set up the basic layer of data. */
  648.     init_features();
  649.     /* Scan through list to see what's being requested. */
  650.     for (rest = g_feature_types(); rest != lispnil; rest = cdr(rest)) {
  651.     if (consp(car(rest)) && stringp(car(car(rest)))) {
  652.         classname = c_string(car(car(rest)));
  653.         if (strcmp(classname, "peak") == 0) {
  654.             name_highest_peaks(cdr(car(rest)));
  655.         } else if (strcmp(classname, "lake") == 0) {
  656.         name_lakes(cdr(car(rest)));
  657.         } else {
  658.         run_warning("Don't know to identify \"%s\" features", classname);
  659.         }
  660.     } else {
  661.         run_warning("Clause not recognized");
  662.     }
  663.     }
  664.     finish_lengthy_process();
  665.     return TRUE;
  666. }
  667.  
  668. /* Identify the highest high points as "peaks". */
  669.  
  670. static void
  671. name_highest_peaks(parms)
  672. Obj *parms;
  673. {
  674.     int x, y;
  675.     int maxpeaks = (area.width * area.height) / 200;
  676.     int numpeaks, *peakx, *peaky, i, lo;
  677.     char *name;
  678.     Feature *mountain;
  679.  
  680.     if (!elevations_defined() || world_is_flat()) {
  681.     run_warning("Can't identify peaks, world is flat");
  682.     return;
  683.     }
  684.     peakx = (int *) xmalloc(maxpeaks * sizeof(int));
  685.     peaky = (int *) xmalloc(maxpeaks * sizeof(int));
  686.     numpeaks = 0;
  687.  
  688.     for_all_interior_cells(x, y) {
  689.     if (high_point(x, y)) {
  690.             if (numpeaks < maxpeaks) {
  691.             peakx[numpeaks] = x;  peaky[numpeaks] = y;
  692.             ++numpeaks;
  693.             } else {
  694.             /* Find the lowest of existing peaks. */
  695.             lo = 0;
  696.             for (i = 0; i < numpeaks; ++i) {
  697.                 if (elev_at(peakx[i], peaky[i]) <
  698.                 elev_at(peakx[lo], peaky[lo])) {
  699.                 lo = i;
  700.                 }
  701.             }
  702.             /* If less than our new candidate, replace. */
  703.             if (elev_at(x, y) > elev_at(peakx[lo], peaky[lo])) {
  704.                 peakx[lo] = x;  peaky[lo] = y;
  705.             }
  706.             }
  707.     }
  708.     }
  709.     for (i = 0; i < numpeaks; ++i) {
  710.     name = name_feature_at(x, y, "peak");
  711.     if (name == NULL) {
  712.         sprintf(tmpbuf, "Pk %d", elev_at(peakx[i], peaky[i]));
  713.         name = copy_string(tmpbuf);
  714.     }
  715.     mountain = create_feature("peak", name);
  716.     mountain->size = 1;
  717.     set_raw_feature_at(peakx[i], peaky[i], mountain->id);
  718.     }
  719. }
  720.  
  721. /* True if xy is a local high point. */
  722.  
  723. static int
  724. high_point(x, y)
  725. int x, y;
  726. {
  727.     int dir, nx, ny;
  728.  
  729.     for_all_directions(dir) {
  730.     point_in_dir(x, y, dir, &nx, &ny);
  731.     if (elev_at(nx, ny) >= elev_at(x, y)) {
  732.         return FALSE;
  733.     }
  734.     }
  735.     return TRUE;
  736. }
  737.  
  738. static void
  739. name_lakes(parms)
  740. Obj *parms;
  741. {
  742.     int x, y;
  743.     char *name;
  744.     Feature *lake, *bay;
  745.  
  746.     for_all_interior_cells(x, y) {
  747.     if (water_point(x, y)) {
  748.         name = name_feature_at(x, y, "lake");
  749.         if (name != NULL) {
  750.         lake = create_feature("lake", name);
  751.         lake->size = 1;
  752.         set_raw_feature_at(x, y, lake->id);
  753.         }
  754.     } else if (bay_point(x, y)) {
  755.         name = name_feature_at(x, y, "bay");
  756.         if (name != NULL) {
  757.         bay = create_feature("bay", name);
  758.         bay->size = 1;
  759.         set_raw_feature_at(x, y, bay->id);
  760.         }
  761.     }
  762.     }
  763. }
  764.  
  765. /* True if xy is isolated water. */
  766.  
  767. static int
  768. water_point(x, y)
  769. int x, y;
  770. {
  771.     int dir, nx, ny;
  772.  
  773.     if (strcmp(t_type_name(terrain_at(x, y)), "sea") != 0
  774.         && strcmp(t_type_name(terrain_at(x, y)), "shallows") != 0)
  775.       return FALSE;
  776.     for_all_directions(dir) {
  777.     point_in_dir(x, y, dir, &nx, &ny);
  778.     if (terrain_at(x, y) == terrain_at(nx, ny) || t_liquid(terrain_at(nx, ny))) {
  779.         return FALSE;
  780.     }
  781.     }
  782.     return TRUE;
  783. }
  784.  
  785. static int
  786. bay_point(x, y)
  787. int x, y;
  788. {
  789.     int dir, nx, ny;
  790.     int seacount = 0, landcount = 0;
  791.  
  792.     if (strcmp(t_type_name(terrain_at(x, y)), "shallows") != 0)
  793.       return FALSE;
  794.     for_all_directions(dir) {
  795.     point_in_dir(x, y, dir, &nx, &ny);
  796.     if (strcmp(t_type_name(terrain_at(x, y)), "sea") == 0)
  797.       ++seacount;
  798.     else
  799.       ++landcount;
  800.     }
  801.     return (seacount > 0 && landcount > 2);
  802. }
  803.  
  804. static char *name_feature_at_using PROTO ((Obj *namerlist, int x, int y, char *typename));
  805. /* (should reindent) */
  806. static char *
  807. name_feature_at(x, y, typename)
  808. int x, y;
  809. char *typename;
  810. {
  811.     char *rslt;
  812.     Obj *namerlist;
  813.     Side *side;
  814.  
  815.     /* Look for any side-specific namers. */
  816.     if (people_sides_defined()) {
  817.       for_all_sides(side) {
  818.     if (side->featurenamers != NULL
  819.         && side->featurenamers != lispnil
  820.         && people_side_at(x, y) == side->id) {
  821.         rslt = name_feature_at_using(side->featurenamers, x, y, typename);
  822.         if (rslt != NULL)
  823.           return rslt;
  824.     }
  825.       }
  826.     }
  827.     /* Now try generic namer list. */
  828.     namerlist = g_feature_namers();
  829.     /* If no generic namers, get out of here. */
  830.     if (namerlist == lispnil)
  831.       return NULL;
  832.     return name_feature_at_using(namerlist, x, y, typename);
  833. }
  834.  
  835. static char *
  836. name_feature_at_using(namerlist, x, y, typename)
  837. Obj *namerlist;
  838. int x, y;
  839. char *typename;
  840. {
  841.     Obj *rest, *namerspec;
  842.  
  843.     /* If no namers found, get out of here. */
  844.     if (namerlist == lispnil)
  845.       return NULL;
  846.     for (rest = namerlist; rest != lispnil; rest = cdr(rest)) {
  847.     if (consp(car(rest))
  848.         && stringp(car(car(rest)))
  849.         && strcmp(c_string(car(car(rest))), typename) == 0) {
  850.         namerspec = cadr(car(rest));
  851.         /* This might be a string naming a namer, try making it into
  852.            a symbol. */
  853.         if (stringp(namerspec))
  854.           namerspec = intern_symbol(c_string(namerspec));
  855.             if (boundp(namerspec))
  856.           return run_namer(symbol_value(namerspec));
  857.         /* If the namer doesn't exist, then this will continue looking for
  858.            one that does, which is maybe good, because this might fall back
  859.            from a side-specific to a generic namer, but can be confusing to
  860.            game designers, because then a feature might be created with no
  861.            name, with no warning of a problem with namers. */
  862.     }
  863.     }
  864.     return NULL;
  865. }
  866.  
  867. /* For efficiency and semantics reasons, the methods might not assign values
  868.    to the cells around the edge of the area (if there *are* edges; neither
  869.    a torus nor sphere will have any).  Note that there is no way to
  870.    disable this from the game module; if having nonconstant edges is important
  871.    enough to be worth the user confusion, don't call this from your
  872.    area generation method. */
  873.  
  874. /* (this needs to set elevs too, maybe other stuff on edges?) */
  875.  
  876. void
  877. add_edge_terrain()
  878. {
  879.     int x, y, t = g_edge_terrain(), halfheight = area.height / 2;
  880.  
  881.     /* Use ttype 0 if edge terrain is nonsensical. */
  882.     if (!between(0, t, numttypes-1))
  883.       t = 0;
  884.     /* Right/left upper/lower sides of a hexagon. */
  885.     if (!area.xwrap) {
  886.     for (y = 0; y < halfheight; ++y) {
  887.         /* SW edge */
  888.         set_terrain_at(halfheight - y, y, t);
  889.         /* NW edge */
  890.         set_terrain_at(0, halfheight + y, t);
  891.         /* SE edge */
  892.         set_terrain_at(area.width-1, y, t);
  893.         /* NE edge */
  894.         set_terrain_at(area.width-1 - y, halfheight + y, t);
  895.     }
  896.     }
  897.     /* Top and bottom edges of the area. */
  898.     for (x = 0; x < area.width; ++x) {
  899.     set_terrain_at(x, 0, t);
  900.     set_terrain_at(x, area.height-1, t);
  901.     }
  902. }
  903.